package com.yulan.backTrack;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 *  1 - n 全排列
 */
public class Permutation {
    List<List<Integer>> ans = new ArrayList<>();

    public List<List<Integer>> permutation(int[] arr){
        dfs(new ArrayList<>(),arr);
        return ans;
    }

    public void dfs(List<Integer> curList, int[] arr){
        if(curList.size() == arr.length){
            ans.add(new ArrayList<>(curList));
            return;
        }

        for(int i = 0; i<arr.length; i++){
            if(curList.contains(arr[i])) continue;

            curList.add(arr[i]);

            dfs(curList,arr);

            curList.remove(curList.size()-1);
        }
    }

    @Test
    public void test(){
        int[] arr = {1,2,3,4,5};
        for(List<Integer> list : permutation(arr)){
            System.out.println(list);
        }
    }
}
